A random variate, which is a sample value of a random or stochastic variable, is a real number derived from a probability distribution. Random variates can be either discrete or continuous depending upon whether the random variable from which they are derived is discrete or continuous. If the number of values a random variable can assume is finite or countably infinite, it is discrete. Discrete random variates find application in conducting simulations, and in optimization processes such as those for determining interconnection configurations and partitioning of logic between several chips in very large scale integrated circuits, and such as those for optimizing computer code, and in generating random signals for masking, encryption, testing, image coding and texture generation, games, computer-aided instruction, artistic patterns and musical composition. Statistical studies, in particular, of arrivals and departures and of probabilities of successes and failures of testing procedures, defect analysis and traffic analysis are based on discrete distributions such as, the Poisson distribution, represented by the following function giving the probability that the random variable assumes the value x: ##EQU1## where x=0, 1, 2, . . . ,
.lambda.=the mean of the distribution defined as the average of its possible values weighted by their probability of occurrence, i.e., the summation of the products of the function f(x) and its independent variable x, and PA1 e=the exponential value 2.71828+.
The Poisson distribution is used hereinafter in an illustrative embodiment of the invention.
In the prior art several methods for generating variates have been used, such as, the inverse transformation method and the composition method. In the inverse transformation method a uniform random variate, i.e., one taken from a uniform distribution for which all values of the random variable with nonzero probability have equal probability, is mapped or transformed into a random variate from another distribution, e.g., of the Poisson type, by means of the inverse transformation of the cumulative distribution function (CDF). Uniform random variates or more correctly approximations thereto may be obtained by one of several well-known means including computation, operation of a mechanical device, or as the evidence of random physical phenomena. The cumulative distribution function gives for each real number x the probability that the random variable has a value less than or equal to the value x. It is defined for all real numbers, and for a discrete random variable it has a steplike form. As an example, the Poisson distribution given in equation (1) with .lambda.=2 takes on the following values, shown to six decimal places:
______________________________________ f(0) = 2.sup.0 e.sup.-2 /0! = 1/e.sup.2 = 0.135335 f(1) = 2.sup.1 e.sup.-2 1! = 2/e.sup.2 = 0.270670 f(2) = 2.sup.2 e.sup.-2 /2! = 2/e.sup.2 = 0.270670 f(3) = 2.sup.3 e.sup.-2 /3! = 4/3e.sup.2 = 0.180447 . . ______________________________________
The associated cumulative distribution function, denoted by F(x) is
______________________________________ F(x) for x &lt; 0 = 0 = 0.000000 F(x) for 0 .ltoreq. x &lt; 1 = f(0) = 0.135335 F(x) for 1 .ltoreq. x &lt; 2 = f(0) + f(1) = 0.406006 F(x) for 2 .ltoreq. x &lt; 3 = f(0) + f(1) + f(2) = 0.676676 F(x) for 3 .ltoreq. x &lt; 4 = f(0) + f(1) + f(2) + f(3) = 0.857123 . . ______________________________________
If F(x)=y denotes the cumulative distribution function, then its inverse, denoted by F.sup.-1 (y)=x is obtained by interchanging the dependent and independent variables, giving for the indicated example
______________________________________ F.sup.-1 (y) for 0 &lt; y .ltoreq. 0.135335 = 0 F.sup.-1 (y) for 0.135335 &lt; y .ltoreq. 0.406006 = 1 F.sup.-1 (y) for 0.406006 &lt; y .ltoreq. 0.676676 = 2 F.sup.-1 (y) for 0.676676 &lt; y .ltoreq. 0.857123 = 3 . . ______________________________________
Since it denotes cumulative probability, F(x) or y ranges from 0 to 1, and thus the function F.sup.-1 (y) is defined for y ranging from 0 to 1.
Consider now starting with a random variable U which is uniformly distributed in the range from 0 to 1, and operating upon it with the inverse function F.sup.-1, that is for each specific value u of the random variable U, obtain the value F.sup.-1 (u), thus obtaining a new random variable, called U'. Then, according to the laws of probability, the CDF of this new random variable U' is the same as F(x), and the probability distribution of U' is the same as f(x). Accordingly, to generate a random variate from any given probability distribution f(x), first generate a random variate value u and then compute F.sup.-1 (u). The resulting value is the desired random variate from the distribution f(x). For continuous random variables the equation for the CDF F(x)=y may generally be solved algebraically for x as an explicit function of y, or equivalently as the inverse x=F.sup.-1 (y). Then the generated uniform random variate u is substituted for each appearance of y in the expression F.sup.-1 (y), and the resulting value of F.sup.-1 (y) is the desired random variate, x. In general it is not possible to obtain x as an explicit function of y for discrete random variables which have step-like cumulative distribution functions, and in particular those containing factorial expressions as for the Poisson distribution. Instead, the inverse operation may be performed in effect by comparing the uniform random variate u to the arguments of the inverse cumulative distribution function at its transitional or stepped points. For example, if the value of u is 0.529437 then comparing it to the arguments of the inverse functional values, F.sup.-1, given above, we see that it falls in the range 0.406006&lt;y.ltoreq.0.676676, yielding the inverse functional value of 2, which is the value of the desired random variate x.
It is seen that the arguments of the inverse CDF are embodied in the values of the CDF itself. Accordingly, to make the indicated comparisons, the transitional CDF values must be available in some form. The CDF values, i.e., y, can be computed on demand by repeated use of equation (1) or precalculated and stored in a table. In general, in-line computation of the CDF values is used when the Poisson parameter .lambda. is subject to change at each instance of generating a Poisson random variate, or when the number of parameters is large or when storage capacity is limited. Otherwise, the table storage approach is a time saver.
In either the in-line or indicated table approach, the search for the appropriate CDF value may proceed sequentially, as in the above example where the uniform variate of 0.529437 is compared first to 0.135335, then to 0.406006, and finally to 0.676676. However, sequential searching is slow and becomes slower with increasing Poisson parameter values. The sequential search has heretofore been speeded up by index searching, whereby searching of the CDF table does not always start at the beginning of the table, but at some subsequent point which depends upon the value of the uniform variate. In this method an auxiliary table is constructed to contain indices or addresses of various entries in the CDF table at which searching is to start. A simple operation on the uniform variate produces an address which is used to enter the auxiliary table. The value obtained from the auxiliary table is the index into the CDF table, and the uniform variate is compared to the CDF table value at the position indexed. If the uniform variate value is less than or equal to the CDF value, then the desired random variate is the index of the CDF value, possibly offset by a constant. If, on the other hand, the uniform variate exceeds the CDF value, then the search continues in a sequential manner as before.
An alternative table approach, called the direct table method, uses a single table which has a separate entry for each possible uniform random variate value in the range from 0 to 1, but with the uniform random variate values limited to a given number of decimal places. For example, with four decimal places the table contains 10,001 entries for the uniform random variates 0.0000, 0.0001, 0.0002, . . . , 0.9999, 1.0000. A given uniform random variate, shifted and possibly incremented by one, gives the address of the table entry which contains the desired random variate value directly. This method is very fast, but requires expensive storage even for the relatively small precision of four decimal places.
In composition methods, the given probability distribution, such as the Poisson, is replaced by a set of component distributions, each of which has a weight with the several weights summing to one. To obtain the desired random variate, one of the component distributions is chosen with probability equal to its weight, and then a value is randomly selected according to the component distribution.
Composition methods avoid the searching, but require much preliminary computation in decomposing the overall distribution into components. One embodiment of the composition method, known as Marsaglia's method has relatively large storage and low precision. See in this connection the paper by G. Marsaglia entitled "Generating Discrete Random Variables in a Computer" (Communications of the ACM, Vol. 6, No. 1, January 1963, pp. 37-38). A second embodiment of the composition method, known as Walker's method, has low storage, but requires generation of two uniform random variates. See in this connection the paper by A. J. Walker entitled "An Efficient Method for Generating Discrete Random Variables with General Distributions" (ACM Transactions on Mathematical Software, Vol. 3, No. 3, September 1977, pp. 253-256).
It is an object of this invention to improve the generation of discrete random variates from a general distribution over known methods and depending upon the particular known method the improvement is made in one or several of the aspects of timing, storage requirements, logic complexity and precision.
It is another object of this invention to generate Poisson random variates from a uniform general distribution over a wide range of parameter values.